package com.example;


/**
 * ysf递推公式解题方法及思路
 * 解题思路：我们需要知道n个人最后剩余人的结果，我们不考虑每次杀的人。如果我们知道1，2,3,4...人时剩余人的结果，
 *           然后找出其中的联系就很轻松就可以算出n个人时最后剩余人的结果
 * 解题方法：我们将n个人编号为0,1,2...n-1 每过m（m>=1）个人就删除一个号 第一次删除的是m-1
 *           我们将剩余的号从m开始重新编号多余的放到末尾，
 *           得到的结果是, m，m+1,m+2...n-1,0...m-2这里要注意的是末尾肯定是正数 如果m<2 这里最后一位就不存在
 *           我们将结果 减去m 并重新编号 得到的结果是 0,1,2...n-m-1...n-2(这里再次强调不考虑要杀的人是谁，将m-1之前的数放到末尾重新排号)。
 *           由此可以看出我们想要知道f(n)的结果 只需要知道f(n-1)的结果就好了然后再加上m就是f(n)的结果
 *           f(n)=f(n-1)+m 
 *           上面的公式对么，答案是有时候对 我可以举个例子大家看一下。
 *           假设m=1 (相当于顺序杀人，剩余的人肯定是最后一个人)
 *           f(1)=0  f(2)=f(1)+1=1  f(3)=f(2)+1=2 这肯定是对的
 *           但如果m=5
 *           f(1)=0  f(2)=f(1)+5=5 这里就不对了吧 我们只有0和1两个人 结果肯定是这两个人
 *           所以我们对所得到的的结果取余操作，保证得到的结果在我们需要的范围内
 *           f(2)=(f(1)+5)%2=1 手动测试一下结果也应该是1
 *           我们再看下f(3) f(3)=f(2)+5=6 也不在我们0,1,2范围内 ，所以达到的结果取余 就是0，我们可以
 *           手动测试一下。
 *           到这里我们的公式应该变一下了 f(n)=(f(n-1)+m)%n
 *
 *           最终的递推公式是f(n)={ 0 n=1;
 *                                 (f(n-1)+m)%n n>1;     }
 *          我们平常都是从1开始计数 所以最后得到的结果需要加1
 *          n=1 时间复杂度是O(1),n=2时间复杂度是O(2)...平均时间复杂度是O(n)。
 *
 * 弊端：   不会考虑每次杀的人是谁，只能得到每种情况最后的杀人数，所以如果想算倒数第二个人杀的是谁
 *          是没法算的
 *
 */

 public class RfToYSF {

    public static void main(String[] args) {
        int n = 41;
        int m = 5;
        int rf = rf(n,m);
        System.out.println(n + "个人时剩余人是" + (rf + 1));
    }

        private static int rf(int n,int m) {
        //递推公式
        if (n == 1) {
            return 0;
        } else {
            int i = (rf(n - 1,m) + m) % n;
            System.out.println(n + "个人时剩余人是" + (i + 1));
            return i;
        }
    }

    
}